%% ------------------------------------------------------------------------- %%
\chapter{Conceitos}
\label{cap:conceitos}

Neste capítulo apresentamos os conceitos fundamentais para concepção do 
nosso protocolo. Esses conceitos são: redes \textit{ad-hoc} móveis,
\textit{Token Ring} e algoritmo de eleição em anel.

Redes \textit{ad-hoc} móveis são redes de propósito eminente e móveis no que
diz respeito a deslocamentos de nós.

É importante mencionar a origem e algumas especificações básicas de
\textit{Token Ring}. Por exemplo, estrutura física e estrutura lógica, 
e o funcionamento.

Para que possamos atribuir responsabilidade a nós em um anel, escolhemos
implementar um critério justo baseado em eleições.

A seguir apresentamos mais informações para cada tópico.
%% ------------------------------------------------------------------------- %%
\section{Redes \textit{Ad hoc} móveis - MANets}
\label{sec:conceitoadhoc}

\begin{figure}[!hbtp]
\centering
\includegraphics[scale=0.3]{r-adhoc-infra.pdf}
\caption{Duas redes com estruturas diferentes}
\label{fig:redesdiferentes}
\end{figure}
% O que é ?
Rede celular ou rede de sistema celular \label{fig:redesdiferentes} (a) é 
atualmente a topologia de comunicação sem fio dominante. Ela tem sido a base de
todos os sistemas de comunicação móvel pessoal tais como UMTS (sistema universal de
telecomunicações móvel), GSM (Sistema Global Para Comunicações Móvel), etc 
\cite{toumpis}. Como mostramos na figura \label{fig:redesdiferentes} (2.1 a), em uma
rede celular somente o último salto (ligação satélite e controlador da rede, e
ligação estação base e aparelhos móveis) é sem fio, todo aparelho móvel
rementente precisa contactar uma estação base para poder alcançar aparelho móvel
destino, e um controlador de rede é o operador das principais funções do
sistema. Em redes dessa natureza (arquitetura centralizada), se o controlador 
de rede falhar está última fica inoperante. Uma alternativa (distribuída e
descentralizada) à rede de sistema celular é rede \textit{ad hoc} móvel.

Uma rede \textit{ad hoc} móvel \ref{fig:redesdiferentes} (b) é uma coleção
autônoma de dispositivos móveis (não necessariamente homogenêos) que se comunicam 
através de \textit{links} sem fio, e se colaboram de modo distribuído de forma a
prover funcionalidades necessárias na ausência de infraestrutura fixa
\cite{hoebeke}. Ao contrário de redes sem fio com infraestruturas
\ref{fig:redesdiferentes} (a), onde cada estação comunica diretamente com alguma 
estação base ou ponto de acesso, uma MAnet, não depende de infraestrutura fixa
para executar as operações inerentes.

%história
O conceito MANet começou em 1972 com o projeto \textit{Packet Radio Network} da
DARPA \cite{hoebeke}. As suas vantagens suscitaram interesses em organizações de
resgate e instituições militares para uso em situações de desastre e ambientes 
hostís. Somente em meados dos anos 1990 com a comercialização de tecnologia de
rádio que a comunidade de pesquisa em tecnologias sem fio ficou ciente da grande
potencialidade que redes desta natureza possuem.

%Como se faz ?
Em uma rede dessa natureza, quando um dispositivo deseja se comunicar ou usufruir
de algum serviço provido pela rede, ele se auto-cria, descobre outros nós, se
inteira de serviços disponíveis e solicita conectividades. Uma vez que se conectou,
o dispositivo deve ser capaz de funcionar como rementente, destino e também como
roteador para encaminhamento de dados pertencentes a nós com área de transmissão
inalcançável pelos dispositivos destinos. 

Essa funcionalidade de encaminhamento
garante que o roteamento em uma rede MANet seja multisalto. Além de roteamento
ser multisalto, as características de uma rede \textit{ad hoc} móvel podem ser 
extendidas a topologia dinâmica de rede, heterogeneidade de dispositivos em uma
mesma rede MANet, além dos já mencionados independência e livre de infraestrutura.
 
%Porquê ?
Apesar de conhecermos bem a arquitetura de redes com infraestrutura fixa, em especial
rede celular, que por todas as métricas tem provado ser a tecnologia mais bem
sucedida da última década \cite{toumpis}, a pesquisa em redes ad hoc sem fio continua
porque uma rede desta natureza pode ser rapidamente inicializada com pouca 
intervenção de usuário; tem a capacidade de se auto-criar, auto-organizar e 
auto-administrar; não tem dispesas com estações base e cabeamento; e têm várias
aplicações.

%Para quê ?

\section{\textit{Token Ring}}
\label{sec:conceitotokenring}


\begin{figure}[!hbtp]
\centering
\includegraphics[scale=0.4]{estacao-token-ring.pdf}
\caption{Uma rede \textit{Token Ring}}
\label{fig:tokenringibm}
\end{figure}

Originalmente, rede \textit{Token Ring} foi desenvolvida pela IBM no começo
dos anos oitenta. E mais tarde, foi padronizado e incluso nas especificações 
de IEEE sob a denominação de IEEE 802.5~\cite{trspec}.

De acordo com as especificações em~\cite{trspec}, a estrutura física de
um \textit{Token Ring} consiste em topologia em estrela, enquanto a sua
estrutura lógica é um anel. Na figura~\ref{fig:tokenringibm}, apresentamos
um exemplo de topologia em estrela (b) para
representação física, e uma topologia em anel (a) para representação lógica. 

%como funciona
\textit{Token Ring} é formando por estações de trabalho serialmente conectadas
que disputam um direito exclusivo e momentâneo para uso de meio de transmissão de
dados. Ter esse direito exclusivo, só é possível se uma determinada estação estiver
com \textit{token} - um controlador de transmissões contido de uma sequência de
bits única que circula em meio de transmissões. A circulação de um \textit{token}
é feita em sentido único, ou horário, ou anti-horário. Ele passa de estação em
estação. Na figura~\ref{fig:tokenringibm}, assim como no nosso projeto, escolhemos
a circulação no sentido horário.

Quando uma estação detecta um \textit{token} apropriado, ela
faz as alterações necessárias para depois transmitir os dados e o \textit{token}.
Porém, se uma estação receber um \textit{token} e não tiver dados para transmitir,
ela libera o \textit{token} para que uma outra estação possa usar.

De acordo com a especificação~\cite{trspec}, uma estação pode reter um 
\textit{token} até que ela termine de transmitir os pacotes armazenados em uma
fila local.

Para cada classe de serviço, por exemplo, voz em tempo real, interatividade, 
recuperação de rede, é alocada uma prioridade por acordo mútuo entre usuários de
rede.

Também, detecção de erros e mecanismos de recuperação de falha são providos para
restauração de rede.

%quais as aplicações
Uma rede \textit{Token Ring} é classificada como uma LAN e também aplicável
a uma rede de área metropolitana (MAN).

De acordo com a nossa pesquisa e levantamento bibliográfico, o último trabalho
(\cite{cheng}) de pesquisa relacionado a \textit{Token Ring} sem fio, foi publicado
no ano de 2007.
 
\section{Algoritmo de eleição em anel: O algoritmo de Chang \& Roberts}
\label{sec:conceitoeleicao}
Este algoritmo distribuído supõe que:
\begin{itemize}
 \item os nós estão dispostos em forma de anel, cada nó locamente executa o
 mesmo algoritmo e conhece todos os nós no seu anel.
 \item as mensagens são enviadas em sentido único (sentido horário, no
 nosso caso)
 \item cada nó tem um identificador ID diferente dos demais nós
 \item qualquer nó pode iniciar uma eleição.
\end{itemize}

Assumamos em especial que uma eleição é feita baseada em IDs de nós. E, uma 
mensagem eleição é do tipo E(ID, participante).

Quando algum nó detecta que o líder atual não está presente:
\begin{itemize}
 \item ele constrói uma mensagem E(ID, participante), e envia essa mensagem 
para seu sucessor.
 \item quando um sucessor receber uma mensagem do tipo eleição, ele compara
o ID na mensagem com o ID dele.
 \item se o ID dele for maior que o ID na mensagem recebida, ele constrói 
uma nova mensagem E(ID dele, participante) e envia para o sucessor dele.
 \item se o ID dele for menor que o ID na mensagem recebida, ele envia
a mensagem recebida para o sucessor dele.
 \item se um nó receber uma mensagem contendo ID dele, então ele é o novo
líder. Logo, ele envia uma mensagem para o sucessor dele informando que ele
é o novo líder. Quando essa mensagem voltar a ele termina o processo de eleição.
\end{itemize}
 
%colocar exemplo de eleição

%Eleição de coordenador
\subsection{Eleição de coordenador}
\label{sec:conceitoeleicaocoordenador}
Consideremos $ID$ identificador de um nó, $\varepsilon$ energia restante em um nó e
um tipo de mensagem $\mu(RA, ID, \varepsilon)$. Onde $RA$ é um endereço de anel e
$ID$ é identificador do nó com maior $\varepsilon$ até o momento.

Um nó começa uma eleição gerando uma mensagem $\mu(RA, ID, \varepsilon)$. Onde
$RA$ é o endereço do anel dele onde está ocorrendo eleição. $ID$ é o identificador
dele e $\varepsilon$ é a energia restante nele. Após gerar esta mensagem, ele 
envia-a para o sucessor dele.

Quando um nó receber uma mensagem $\mu(RA, ID, \varepsilon)$, ele verifica
se faz parte do anel com endereço $RA$. Se sim, ele compara
$\varepsilon$ local com $\varepsilon$ da mensagem. Se $\varepsilon$ local for
maior, ele gera uma nova mensagem $\mu(RA, ID, \varepsilon)$ com $ID$ e $\varepsilon$
dele, mesmo $RA$, e envia esta nova mensagem para o sucessor dele. Se $\varepsilon$
local for menor, ele envia a mesma mensagem recebida para o sucessor dele. Se 
$\varepsilon$ local e $\varepsilon$ na mensagem forem iguais, usam-se $IDs$ como critério
de desempate. I.e., se $ID$ local for maior, o nó gera uma nova mensagem e envia-a para 
o sucessor dele, senão envia a mensagem recebida para o sucessor dele.